package com.future;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * Description: NC165 最长公共子序列(一)
 *
 * @author weiruibai.vendor
 * Date: 2022/7/29 16:21
 */
public class Solution_NC165 {

    private static AtomicInteger atomic = new AtomicInteger(0);

    public static void main(String[] args) {
        Solution_NC165 nc165 = new Solution_NC165();

        String s1 = "abcde";
        String s2 = "bdcaaa";
        s1 = "nwlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarc";
        s2 = "bynecdyggxxpklorellnmpapqfwkhopkmcoqhnwnkuewhsqmgb";
        System.out.println(System.currentTimeMillis());
        System.out.println(nc165.LCS_dp(s1, s2));
        System.out.println(System.currentTimeMillis());
        System.out.println(nc165.LCS(s1, s2));
        System.out.println(System.currentTimeMillis());

    }

    /**
     * 最简单容易理解的动态规划版本
     *
     * @param s1
     * @param s2
     * @return
     */
    public int LCS_dp(String s1, String s2) {

        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 1) {
            return 0;
        }
        int N1 = s1.length();
        int N2 = s2.length();
        int[][] dp = new int[N1][N2];
        for (int i = 0; i < N1; i++) {
            for (int j = 0; j < N2; j++) {
                dp[i][j] = -1;
            }
        }
        return process_dp(s1.toCharArray(), s1.length() - 1, s2.toCharArray(), s2.length() - 1, dp);
    }

    private int process_dp(char[] chars1, int i, char[] chars2, int j, int[][] dp) {
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int val;
        if (i == 0 && j == 0) {
            val = chars1[0] == chars2[0] ? 1 : 0;
        } else if (i == 0) {
            if (chars1[0] == chars2[j]) {
                val = 1;
            } else {
                val = process_dp(chars1, 0, chars2, j - 1, dp);
            }
        } else if (j == 0) {
            if (chars1[i] == chars2[0]) {
                val = 1;
            } else {
                val = process_dp(chars1, i - 1, chars2, 0, dp);
            }
        } else {
            // i-1...j
            int n1 = process_dp(chars1, i - 1, chars2, j, dp);
            // i...j-1
            int n2 = process_dp(chars1, i, chars2, j - 1, dp);
            // i-1...j-1
            int n3 = chars1[i] == chars2[j] ? 1 + process_dp(chars1, i - 1, chars2, j - 1, dp) : 0;
            val = Math.max(Math.max(n1, n2), n3);
        }
        dp[i][j] = val;
        return val;
    }

    public int LCS(String s1, String s2) {
        // write code here
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 1) {
            return 0;
        }
        return process(s1.toCharArray(), s1.length() - 1, s2.toCharArray(), s2.length() - 1);
    }

    private int process(char[] chars1, int i, char[] chars2, int j) {
        int val;
        if (i == 0 && j == 0) {
            val = chars1[0] == chars2[0] ? 1 : 0;
        } else if (i == 0) {
            if (chars1[0] == chars2[j]) {
                val = 1;
            } else {
                val = process(chars1, 0, chars2, j - 1);
            }
        } else if (j == 0) {
            if (chars1[i] == chars2[0]) {
                val = 1;
            } else {
                val = process(chars1, i - 1, chars2, 0);
            }
        } else {
            // i-1...j
            int n1 = process(chars1, i - 1, chars2, j);
            // i...j-1
            int n2 = process(chars1, i, chars2, j - 1);
            // i-1...j-1
            int n3 = chars1[i] == chars2[j] ? 1 + process(chars1, i - 1, chars2, j - 1) : 0;
            val = Math.max(Math.max(n1, n2), n3);
        }
        return val;
    }
}
